package 剑指offer;

import java.util.ArrayList;
import java.util.List;

public class 丑数 {
    /**
     * @param args 只包含2，3，5因子的数称为丑数，1,2，3，4，5，6，8，9，10，12，15,16
     */
    static  int GetUglyNumber_Solution(int index) {
        // 0-6的丑数分别为0-6
        if(index < 7) return index;
        //p2，p3，p5分别为三个队列的指针，newNum为从队列头选出来的最小数
        int p2 = 0, p3 = 0, p5 = 0, newNum = 1;
        List<Integer> arr = new ArrayList<>();
        arr.add(newNum);
        while(arr.size() < index) {
            //选出三个队列头最小的数
            newNum = Math.min(arr.get(p2) * 2, Math.min(arr.get(p3) * 3, arr.get(p5) * 5));
            //这三个if有可能进入一个或者多个，进入多个是三个队列头最小的数有多个的情况
            if(arr.get(p2) * 2 == newNum) p2++;
            if(arr.get(p3) * 3 == newNum) p3++;
            if(arr.get(p5) * 5 == newNum) p5++;
            arr.add(newNum);
        }
        return newNum;
    }
        public static int findChoushu(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        int count = 1;
        int number = 1;
        int tmp = 1;

        while (n != count) {
            tmp = number;
            for (int i = 2; i < n + 1; i++) {
                if (tmp % i == 0) {

                    if (i == 2 || i == 3 || i == 5) {
                        tmp = tmp / i;
                        i = 1;
                        if (tmp == 1) {
                            count++;
                        }
                    }

                }
            }
            number++;
        }


        return number - 1;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(findChoushu(90));
        System.out.println((GetUglyNumber_Solution(90)));

    }

}
